1. Technical Field
Example embodiments of the present invention relate to flash memory and more specifically to a method for distributing log block associativity in a flash memory and a flash memory device performing the same.
2. Description of the Related Art
A flash memory is a non-volatile memory and is greatly classified into a NOR flash memory which has a characteristic of a random memory and a NAND flash memory which has a similar characteristic to a storage medium such as a hard disk.
In an internal structure, as shown in FIG. 1, a NAND flash memory includes a plurality of blocks each of which includes a plurality of pages. For example, one block can include 64 pages or 128 pages.
A NAND flash memory performs read and write operations a unit of page and an erase operation in a unit of block. For example, a read operation is performed at a speed of about 25 us, a write operation is performed at a speed of about 250 us, and an erase operation is performed at a speed of about 2,000 us. That is, the respective operations are asymmetric in speed, and an erase operation is slowest.
A hard disk drive (HDD) can overwrite data on a physically same area as existing data when a data update is required (in-place update). However, a NAND flash memory can perform a write operation only in a state that a corresponding area is erased. That is, a NAND flash memory has a feature that new information can be written only in a block which is already erased. Due to this feature, a NAND flash memory cannot overwrite directly at a location that data is previously written, and should write at a new location (out-place update) and then update location information.
Also, in a flash memory, the number of writing/erasing times is limited to equal to or less than the predetermined number of times (for example, 100,000 times), and thus if a certain block is used more than the predetermined number of times, the block cannot be normally used (cannot perform a new write operation) any more. For this reason, when an update on information is required, a wear leveling technique that erases a corresponding block for the next operation but writes information in a new block without erasing a corresponding block and writing in an erased block is commonly used.
Therefore, a NAND flash memory needs to perform a periodic erase operation as well as read and write operations in order to input or output user data. An erase operation is performed at the slowest speed among operations of a NAND flash memory as described above, and this feature is the biggest shortcoming of a NAND flash memory compared to a hard disk.
Due to the above-described inherent features of the NAND flash memory, system software called a flash translation layer (hereinafter, “FTL”) is commonly used between a file system of a host system and a NAND flash memory. The FTL functions to hide the inherent features of the NAND flash memory in the file system of the host system and maps a logical address transmitted from the file system with a physical address of the NAND flash memory so that the same input/output operation as a hard disk can be performed.
There are three mapping techniques for mapping a logical address of a file system with a physical address of a NAND flash memory: page-level mapping; block-level mapping; and hybrid-level mapping.
A page-level mapping technique maps data of a NAND flash memory in a unit of page. A page-level mapping technique has a disadvantage in that the size of a mapping table which stores mapping information increases as a storage space of a large-capacity NAND flash memory such as a solid state drive (SSD) increases.
A block-level mapping technique maps data of a NAND flash memory in a unit of block and accesses a corresponding area with a block number and an offset of the block inside. A block-level mapping technique has an advantage in that the size of a mapping table is greatly reduced compared to a page-level mapping technique but has a disadvantage in that an overhead of a data update is increased. That is, since data mapping is performed in a unit of block, if an update request on a certain page (for example, p2 201 of FIG. 2A) is generated, a newly updated page has to be written in a new block, and remaining pages (p0, p1 and p3 of FIG. 2A) have to be copied to the new block from an existing block (see FIG. 2A).
A hybrid-level mapping technique has been suggested to improve such an overhead problem. In a hybrid-level mapping technique, all physical blocks of a NAND flash memory are classified into data blocks and log blocks. Data in a data block is input or output using a block-level mapping technique, and data in a log block is input or output using a page-level mapping technique.
As a FTL hybrid-level mapping technique, there are a block associative sector translation (BAST) technique, a fully associative sector translation (FAST) technique, and a set associative sector translation (SAST) technique.
A hybrid-level mapping technique called a BAST technique is a 1:1 log block mapping technique. In a BAST technique, if a first data write request is generated and sent to a FTL, data is written in a data block using a block-level mapping technique. As shown in FIG. 2A, if an update on data written in a data block is required, a data update is performed in a log block. That is, previous data written in a data block (for example, page p2 203 of FIG. 2B) is invalidated, and then data to be updated is sequentially written in a log block allocated, starting from a first page.
In a BAST technique, even though a certain page is frequently updated, unlike a block-level mapping technique, remaining pages do not need to be copied until all pages of a corresponding log block are used. If an update on a new data block is required in a state that all log blocks are allocated, one of the log blocks is merged to allocate a new log block. Such a merge operation includes a full merge operation, a partial merge operation and a switch merge operation. An appropriate merge operation is selected according to an order of data written in a log block.
FIGS. 3A and 3B are schematic diagrams illustrating a data update procedure of a conventional BAST technique. It is assumed that total 6 data blocks B0 to B5 exist, and maximum 4 log blocks L0 to L3 can be allocated.
Referring to FIG. 3A, if an update on p1, p5, p9, and p13 is required, log blocks are designated for an update of corresponding data blocks. Thereafter, if an update on p17 is required, as shown in FIG. 3B, one of the log blocks is merged to allocate a new log block. The merge operation is performed in an order of a log block allocated to a data block. If a data update is performed in an order of p1, p5, p9, p13, p17, p20, p21, p2, and p6, a request is performed as shown in FIG. 3B.
If a write request pattern is random, a 1:1 mapping technique such as a BAST technique described above shows poor performance since frequent log block merges are inevitable. This is called a log block thrashing problem. For example, if a write pattern is a sequence of p0, p4, p8, p12, p16, p20, p1, p5, in a BAST technique, one of four log blocks should be replaced whenever a write operation of p16 or later is performed, leading to an expensive merge operation. In addition, as shown in FIG. 3B, when replaced, each victim log block maintains only one page, and the other three pages remain empty. Thus, in a BAST technique, log blocks show very low space utilization when a victim log block is replaced with a new log block (buffer).
To solve the above problem of a 1:1 mapping technique, a FAST technique as an N:1 log block mapping technique has been introduced. FIG. 4 shows a schematic diagram illustrating a data update procedure of a conventional FAST technique.
A FAST technique is a technique to solve a block thrashing problem of a BAST technique. In a FAST technique, data blocks are associated with a log block in an N:1 method (N denotes the total number of data blocks, and 1 denotes the number of log blocks). Also, all log blocks are divided into a random log block and a sequential log block, one sequential log block is maintained, and if an update of a page having an offset “0” is required, a data is written in a sequential log block.
In a FAST technique, pages updated in all data blocks can be written in one log block. Therefore, a data update is not performed only in a certain log block allocated to a corresponding data block, and updated pages are written in, starting from a first log block. That is, all pages of a first log block have to be filled before proceeding to a second log block. As shown in FIG. 4, a data update request is generated in an order of p1, p5, p9, p13, p17, p20, p21, p2, and p6 like a case of a BAST technique shown in FIGS. 3A and 3B. In this case, unlike a BAST technique, a 1:1 association is not made between a data block and a log block, and data is written in, starting from a first log block. Also, since p20 is a page having an offset “0” in a data block B5, it is written in a sequential log block (SLB), and p21 updated thereafter is written in the sequential log block (SLB) since p21 is a page having an offset “1” in the data block B5 and is data for maintaining the sequentiality of the sequential log block.
In a FAST technique, since only one sequential log block is maintained, whenever there is an update request on a page having an offset “0”, a sequential log block has to undergo a partial merge. Also, if there is a write request on a page which cannot maintain the sequentiality of a sequential log block, a full merge operation is performed after writing in a sequential log block. This causes a block thrashing problem of a sequential log block, and there is a possibility that a partial merge and a full merge are performed in a state that the utilization of a sequential log block is low.
Then, when all log blocks are fully filled with data, a merge operation with associated data blocks is performed, starting from a first random log block.
The number of data blocks associated with each log block is defined as associativity, and random log blocks RLB0 and RLB1 of FIG. 4 have associativity values of 4 and 3, respectively.
As described above, in a FAST technique, a maximum value of associativity can be increased up to the number of pages of a log block. A merge operation value depends on the magnitude of the log block associativity, and the merge cost of one time merge operation can be expressed by Equation 1. Therefore, a FAST technique has a problem in that a time of a single merge operation cannot be expected.Merge cost=A(LB)×N×Ccopy+(A(LB)+1)×Cerase  Equation 1,
where A(LB) denotes the associativity of a log block, N denotes the number of pages per block (pages_per_block), Ccopy is the cost of the page copy, and Cerase denotes the cost of the block erase.
In a FAST technique, a difference between a worst-case block merge time and a best-case block merge time is large due to high block associativity. Therefore, neither of both cases is suitable to a real-time system which has to guarantee that an operation is completed within a fixed time.
As another FTL hybrid-level mapping technique, there is a SAST technique which uses an N:K log block mapping. In a SAST technique, blocks is divided into a data block group and a log block group, and respective groups are mapped with each other. The maximum number of blocks which can belong to a data block group is defined as N, and the maximum number of blocks which can belong to a log block group is defined as K.
FIG. 5 is a schematic diagram illustrating a data update procedure of a conventional SAST technique. FIG. 5 shows a case where the maximum block number N of a data block group is restricted to 3, and the maximum block number K of a log block group is restricted to 2.
As shown in FIG. 5, a data update occurring in a block group is performed in a corresponding log block group. Therefore, the maximum associativity of a log block is restricted depending on the maximum number N of blocks which constitute a data block group.
However, a SAST technique has a problem in that if data in a certain data block group is frequently updated compared to that in a different block group, a log block allocated to the different block group has to be merged with the low utilization. That is, a block thrashing (log block trashing) problem may occur like a BAST technique. In addition, since a sequential log block is not separately distinguished, the number of times of a partial merge and a switch merge can be decreased.
Therefore, since there is a limitation that an N:K mapping technique is a compromise of a 1:1 log block mapping technique and an N:1 log block mapping technique, an N:K mapping technique cannot solve both a block thrashing problem and a high block associativity problem completely.
A merge operation requires a long time, and a difference between a maximum value and a minimum value of the merge cost is large depending on the associativity. Particularly, in a real-time system, it is very important to estimate a deadline of processing.